package com.wuda.segmentation;

import java.util.ArrayList;
import java.util.List;

import com.wuda.util.CharacterTree;
import com.wuda.util.CharacterTree.TreeNode;

/**
 * 
 * 此算法来自<a href="http://xiecc.blog.163.com/blog/static/14032200671110224190/"
 * >疯狂的阶梯</a>
 * 
 * 
 * @author wuda
 * 
 */
public class GTSegmenter implements Segmenter {

	private CharacterTree DIC_TREE; // 词典

	/**
	 * <p>
	 * 指定一个词典来生成分词器
	 * </p>
	 * 
	 * @param dic
	 *            {@link CharacterTree},词典
	 */
	public GTSegmenter(final CharacterTree dic) {
		DIC_TREE = dic;
	}

	/**
	 * <p>
	 * 分词算法主体
	 * </p>
	 * 
	 * @param input
	 *            输入字符串
	 * @return {@link Token}'s
	 */
	public List<Token> seg(String input) {
		if(input==null || input.isEmpty()){
			return null;
		}
		char[] charArray = input.toCharArray();
		List<Token> segmentTokens = new ArrayList<Token>();
		int position = 0;
		int offset = 0;
		char c;
		TreeNode node = DIC_TREE.getRoot();
		StringBuilder buffer = new StringBuilder();
		int index = 0;
		while (position < charArray.length) {
			while (node != null) {
				if (node.isWordEnd()) { // 这个节点和它的祖先节点中的char可以组成一个单词
					Token segToken = new Token(buffer.toString().toCharArray(),
							position, position + offset);
					segmentTokens.add(segToken);
				}
				index = position + offset;
				if (index >= charArray.length) {
					break;
				}
				c = charArray[index];
				node = DIC_TREE.findChild(node, c);
				buffer.append(c);
				offset++;
			}
			node = DIC_TREE.getRoot(); // reset to root
			buffer = new StringBuilder(); // reset
			offset = 0; // reset
			position++; // 字符数组位置向前移动一位
		}
		return segmentTokens;
	}
}
